package com.leetcode;
import java.util.HashMap;
import java.util.Map;

public class 无重复字符串最长子串 {

	public int lengthOfLongestSubstring(String s) {
		if(s == "") {
			return 0;
		}
		//
		int count = 0;
		int temp = -1;
		int idx = 0;
		//
		StringBuilder builder = new StringBuilder();
		//外层循环控制目前是从第几个字符开始
		while(idx < s.length()) {
			//里面循环 从idx开，依次找到没有相同的子字符串的长度
			for(int i =idx;i<s.length();i++) {
				//
				if(builder.toString().indexOf(s.charAt(i)) != -1) {
					System.out.println("----");
					//取出当前子串的长度
					temp = builder.length();
					//如果这个长度比当前的count大，则赋值给count
					if(temp > count) {
						count = temp;
					}
					//清空这个 builder中的内容
					builder.delete(0, builder.capacity());
					//退出内部循环
					break;
				} else {
					builder.append(s.charAt(i));
				}
			}
			//idx++
			idx++;
			System.out.printf("第[%d]轮, count=%d\n",idx,count);
			//判断一下
			if(builder.length() == s.length()) {
				System.out.println("说明整个字符串都没有重复字母");
				count = builder.length();
				break;
			}
		}
		//
		/*
		 * if(builder.length() > count) { count = builder.length(); }
		 */
		//
		return count;
	}
	//dvdk， abcadea
	public int method2(String s) {
		int n = s.length();
		if(n <= 1) {
			return n;
		}
		//
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		//
		int i = 0, j = 0;
		//
		int max_length = 0;
		//
		for(; j < n; j++) {
			//如果map中包含这个字位的话
			if(map.containsKey(s.charAt(j))) {
				//上次出现的位置+1
				i = Math.max(i, map.get(s.charAt(j))+ 1);
			}
			//把这个字符添加到map中，value为变量j的值
			map.put(s.charAt(j), j);
			//
			max_length = Math.max(max_length, j-i+1);
		}
		return max_length;
	}
	
	//
	public static void main(String[] args) {
		无重复字符串最长子串 s = new 无重复字符串最长子串();
		System.out.println(s.lengthOfLongestSubstring("abcdefg"));
		//System.out.println(s.method2("abcadea"));
	}
}
